Trước năm 1804, lỵ sở của tỉnh Hải Dương được đặt tại Lạc Thiên (Chí Linh), lúc ấy gọi là thành Vạn hay doanh Vạn. Sau đó rời về Mao Điền (Cẩm Giàng). Năm 1804 (năm Gia Long thứ 3), để củng cố bộ máy cai trị, nhà Nguyễn đã phân chia lại địa giới hành chính của cả nước, do vậy lỵ sở Hải Dương đã được rời từ Mao Điền về vùng ngã ba sông Thái Bình và sông Sặt, thuộc địa phận ba xã Hàn Giang, Hàn Thượng và Bình Lao, tổng Hàn Giang, cách kinh đô Huế 1.097 dặm. Một ngôi thành sở được Trấn thủ, Khâm sai Chưởng cơ Trần Công Hiến cho khởi công để làm trụ sở cho bộ máy và đồn trú quân sự, gọi là Thành Đông, với mục đích vừa là trấn thành, vừa án ngữ phía đông Kinh thành Thăng Long. Đây được xem như thời điểm khởi lập của thành phố Hải Dương.

Thành Đông ban đầu được đắp bằng đất, có hình 6 cạnh, chu vi 551 trượng 6 thước, cao 1 trượng 1 thước 2 tấc, mở 4 cửa. Thành Đông ban đầu không có dân, chỉ có quan lại và quân lính. Năm 1824 (năm Minh Mạng thứ 5), thành được xây thêm bằng đá ong (kiểu xây này cũng được thấy ở thành Bắc Ninh, Thanh Hóa, Nghệ An), có sống khế. Đá ong xây thành được lấy từ thành nhà Mạc ở Đồ Sơn. Đến năm Tự Đức thứ 19 (1865), đắp thêm thành Dương Mã ở các cửa, hình chóp nón úp vào hào trước cửa thành, cao 5 thước 4 tấc, hào rộng 3 trượng 3 thước, sâu 6 thước.

Năm 1889, nhiều đoạn tường Thành Đông bị thực dân Pháp phá bỏ để lấy mặt bằng xây dựng nhà máy rượu và vài tòa dinh thự của người Pháp. Thời gian 1946-1954, do chiến sự ác liệt, phần lớn di tích còn lại của thành cũng bị hư hỏng nặng. Tuy vậy, ngày nay vẫn còn sót lại một số ít đoạn tường thành và dinh Tổng đốc ở trụ sở của Mặt trận Tổ quốc tỉnh.